In a packet switch fabric, a large buffer (queue) is generally desirable in order to minimize packet loss. Packet loss occurs particularly during periods of network congestion, when packets enter the switch faster than they can be sent to the output ports and the switch buffers therefore fill to capacity. It is possible for sufficient traffic on merely one channel to cause loss of packets from that channel due to overflow of the buffer for that particular destination output. As a consequence of buffer overflow, incoming packets are discarded until space in the buffer is made available by the departure of a packet for the switch output port.
Buffer overflow can even occur in an asynchronous transfer mode (ATM) switch having priority capability. When ATM cells contend for the same output port of the switch, the cells with a higher priority will be sent to the output first while the lower priority cells will be stored in the switch buffer. During heavy traffic it is possible for these lower priority cells to completely fill the buffer for a particular output port, leaving no room for incoming cells of any priority. Cells attempting to go to an output port once its buffer is full are permanently lost from the datastream. Cell loss will continue until the buffer is no longer full. It is obvious, therefore, that the larger the buffer available to an output port, the less likely it is that such cell loss will occur.
There is a limit, however, on how large a buffer will fit onto a standard switch chip. For an ATM chip, buffers with a capacity of 64 to 256 cells are common. The maximum buffer size is generally limited by the physical space available on the chip, with the size of the chip itself being limited by both space and manufacturing considerations. The larger and more complicated a chip is, the more likely it is that a manufacturing defect will occur that will force rejection of the whole chip. Manufacture of a large switch chip can therefore can be extremely expensive.
One of the problems imposed by the physical size limits of an ATM switch chip is that only a limited number of inputs and outputs can be made available. This problem has previously been addressed by interconnecting several such chips to provide switches with arbitrarily large numbers of inputs and outputs. For example, Shobatake et. al. use a multistage Clos network of 8.times.8 switch chips to create a 64.times.64 switch Shobatake, Y., Motoyama, M., Shobatake, E., Kamitake, T., Shimizu, S., Noda, M. and Sakaue, K., "A One Chip Scalable 8*8 ATM Switch LSI Employing Shared Buffer Architecture," IEEE Journal on Selected Areas in Communications, Vol. 9, No. 8, October 1991, pp. 1248-1254!. The purpose of interconnecting the switch chips in this device is clearly to expand number of inputs and outputs, not to expand the size of the switch buffer. Shobatake et. al. in fact indicate that "an interconnected ATM switch tends to show worse cell loss rate than a unit ATM switch itself because of the internal congestion" Id at 1284!.
The three-stage Clos network utilized by Shobatake et. al. has each input connected to only one of the chips in the first stage of the network. The outputs of this stage are then connected to various inputs of each of the chips in the second stage, with each first-stage chip output being connected to only one input of one second-stage chip, and with each first-stage chip being connected via its output ports to more than one second-stage chip. Each stage of the interconnected network therefore functions more as part of a switching matrix than as part of an expanded switch buffer.
It is clear from examination of the Shobatake et. al. switch that additional buffer space is not available to any input as a result of the three-stage architecture. The Clos interconnection does not expand the switch buffer size either per input or per output port. For example, if all 8 cells coming into a chip in the Shobatake et. al. switch are intended for output 1 of that chip, the interconnected switch will not be any more likely than a single switch chip to prevent buffer overflow because the input ports on the chip in question do not have access to any of the buffer space available on the other interconnected chips. Essentially, this means that cells coming into input port 1 will never be able to access buffers for input port 9 or higher. The Shobatake et. al. switch therefore does not increase the buffer size at all, merely the available number of inputs and outputs as well as the potential delay through the switch.
Kozaki et. al describe a 64.times.64 switch achieved using 8 32.times.32 switching boards and a 1024.times.1024 switch constructed in a three-stage network from 96 32.times.32 switching boards Kozaki, T., Endo, N., Sakurai, Y., Matsubara, O., Mizukami, M., and Asano, K., "32.times.32 Shared Buffer Type ATM Switch VLSI's for B-ISDN's," IEEE Journal on Selected Areas in Communications, Vol. 9, No. 8, October 1991, pp.1239-1247!. Again, these devices are solely directed to providing more inputs and outputs to a switch fabric than are available on existing ATM switch chips; no additional buffer capacity is provided. In both of these devices, a cell entering at a particular input is always sent to the same one of the switch chips, regardless of the output destination of the cell. If there is heavy traffic on that single input, or, alternatively, heavy traffic directed to a particular output, buffer overflow with resulting cell loss can occur even if the remainder of the inputs have no traffic and the remaining switch buffers are unused.
While creating switches with larger numbers of inputs and outputs has desirable aspects, and doing so via interconnecting smaller switch chips provides certain fabrication efficiencies and economies, it is of little practical value if packet loss counts or chip rejection rates commensurately increase. What has been needed, therefore, is a way to avoid the switch buffer size limitations that are imposed by the physical size limitations of switch chips.